package com.zk.algorithm.sort;

import com.zk.algorithm.Utils;

/**
 * 冒泡排序: 一次冒泡至少会让一个元素移动到它应该在的位置
 *
 * - 原地排序: 空间复杂度 O(1)
 * - 稳定排序: 相邻两个元素大小相等，不做交换
 * - 时间复杂度: 最好 1, 2, 3, 4, 5, 6 O(n); 最坏 6, 5, 4, 3, 2, 1 O(n^2)
 *
 * @author zk
 */
public class BubbleSort {

    /**
     * arr: 4, 5, 6, 3, 2, 1
     *
     * @param arr
     */
    void bubbleSort(int arr[]) {
        int n = arr.length;

        if (n <= 1) {
            return;
        }

        // i: 第 0 趟
        // i: 第 1 趟
        // i: ...
        // i: 第 5 趟
        // i: [0, n)
        //
        // j: 前面 5 个元素选出最大的
        // j: 前面 4 个元素选出最大的
        // j: 前面 3 个元素选出最大的
        // j: ...
        // j: 前面 0 个元素选出最大的
        // j: [0, n - i - 1)

        // 4, 5, 6, 3,  2,   1
        // 4, 5, 3, 2,  1,  [6]
        // 4, 3, 2, 1, [5], [6]
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    Utils.swap(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 优化
     *
     * @param arr
     */
    void bubbleSortOpt(int arr[]) {
        int n = arr.length;

        if (n <= 1) {
            return;
        }

        for (int i = 0; i < n; i++) {
            boolean flag = false; // 这一趟是否有数据交换

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    Utils.swap(arr, j, j + 1);
                    flag = true;
                }
            }

            if (!flag) {
                break;
            }
        }
    }

}